package com.explorati.LeetCode279.numSquares;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 22:19 2020/10/20 0020
 * @ Description ：记忆化搜索解法
 */
public class Solution1 {
    private int[] memo;

    private int squaresNum(int n) {
        if(n <= 0) {
            return 0;
        }
        if(memo[n] != Integer.MAX_VALUE) {
            return memo[n];
        }

        int res = Integer.MAX_VALUE;
        //当前数能分解为 i + (n - i）的加和
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= Math.sqrt(n); j ++) {
                res = Math.min(res, squaresNum(n - j * j) + 1);
            }
        }
        memo[n] = res;

        return res;
    }

    public int numSquares(int n) {
        assert(n >= 1);
        memo = new int[n + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        return squaresNum(n);
    }
}
